# -*- coding: utf-8 -*-

"""剑指 Offer II 075. 数组相对排序
给定两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

提示：
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中"""

class Solution:
    """方案一，arr1 排序好，遍历 arr2 ，查找，删除并返回 arr1 中找到的若干个元素，放到新列表中；遍历结束，将剩余的排好序的元素追加到结果列表中。支持有序，快速查找，频繁删除，用红黑树。
    方案二，桶排序。以 arr2 为基准，创建 len(arr2)+1<其他元素> 的桶，遍历 arr1，从 arr2 中查询放到哪个桶中，最后对其他元素的那个桶排序；合并桶。 arr2 要支持按值快速查找位置，用哈希字典
    
    ！！！注意，重大bug，
        [[],]*(len(arr2)+1)   只创建一个列表对象，每个位置都引用到这唯一一个对象，相当于分身，对任意位置元素操作，都是对那个唯一对象操作
        [[] for _ in range(len(arr2)+1)]    创建了若干个子列表对象，各引用各的"""
    def relativeSortArray(self, arr1, arr2):
        buckets = [[] for _ in range(len(arr2)+1)]
        hi = len(buckets)-1
        arr2d = dict([(v, i) for v, i in zip(arr2, range(len(arr2)))])
        for v1 in arr1:
            i1 = arr2d.get(v1)
            if i1 is not None:
                buckets[i1].append(v1)
            else:
                buckets[hi].append(v1)

        buckets[hi].sort()
        
        answer = []
        for bucket in buckets:
            answer.extend(bucket)
        
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.relativeSortArray(arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]))
